package dmsxl.haxibiao;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/4/14 21:55
 * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
 */
public class hxb3_r1_350 {

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1};
//        int[] nums1 = {4, 5, 9};
        int[] nums2 = {2, 2};
//        int[] nums2 = {9, 4, 9, 8, 4};
        System.out.println(Arrays.toString(intersect(nums1, nums2)));
    }

//    自己做的，效果一般
    public static int[] intersect1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums1){
            if (map.containsKey(num))
                map.put(num, map.get(num)+1);
            else map.put(num, 1);
        }
        System.out.println(map);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums2.length; i++){
            if (map.containsKey(nums2[i]) && map.get(nums2[i])>0){
                list.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i])-1);
            }
        }
        System.out.println(list);
        int[] res = new int[list.size()];
        int i = 0;
        for (Integer item : list){
            res[i] = item;
            i ++;
        }
        return res;
    }

//    双指针题解，先排序，然后和349类似，但是效果很好
    public static int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
